PC Media 7/PC MEDIA CD07.iso/share/prog/cm/cmthash.cc

C/C++ Source or Header | 1994-09-06 | 10.0 KB | 411 lines

// CmTHash.cc
// -----------------------------------------------------------------
// Compendium - C++ Container Class Library
// Copyright (C) 1992-1994, Glenn M. Poorman, All rights reserved
// -----------------------------------------------------------------
// Hash table template implementation.
// -----------------------------------------------------------------


// "CmTHashTable" is the hash table constructor.
//
template <class T> CmTHashTable<T>::CmTHashTable(unsigned sz)
{
  _funcSet = FALSE;
  _total   = 0;
  _buckets = new CmTHashBucket<T>[sz];
  _size    = (_buckets != NULL) ? sz : 0;
}


// "CmTHashTable" is the hash table copy constructor.
//
template <class T> CmTHashTable<T>::CmTHashTable(const CmTHashTable<T>& Tb)
                                  : CmTContainer<T>(Tb)
{
  _funcSet = Tb._funcSet;
  _hFunc   = Tb._hFunc;
  _total   = 0;
  _buckets = new CmTHashBucket<T>[Tb._size];
  _size    = (_buckets != NULL) ? Tb._size : 0;
  copy(Tb);
}


// "CmTHashTable" is the hash table destructor.
//
template <class T> CmTHashTable<T>::~CmTHashTable()
{
  removeAll();
  delete[] _buckets;
}


// "=" assignment operator copies the specified hash table into this table.
//
template <class T>
CmTHashTable<T>& CmTHashTable<T>::operator=(const CmTHashTable<T>& Tb)
{
  if (&Tb != this)
  {
    removeAll();
    delete[] _buckets;
    _funcSet = Tb._funcSet;
    _hFunc   = Tb._hFunc;
    _total   = 0;
    _buckets = new CmTHashBucket<T>[Tb._size];
    _size    = (_buckets != NULL) ? Tb._size : 0;
    copy(Tb);
  }
  return *this;
}


// "setHashFunction" sets the hash function to be used on the input items.
//
template <class T> void
CmTHashTable<T>::setHashFunction(unsigned (*pFunc)(const T&, unsigned))
{
  _funcSet = TRUE;
  _hFunc   = pFunc;
}


// "total" returns the number of items in the table.
//
template <class T> int CmTHashTable<T>::total() const
{
  return _total;
}


// "add" adds a new item to the table.
//
template <class T> Bool CmTHashTable<T>::add(const T& rObj)
{
  if (!_funcSet) return FALSE;
  unsigned idx = (*_hFunc)(rObj, _size);
  Bool success = _buckets[idx].append(rObj);
  if (success) _total++;
  return success;
}


// "remove" removes the first occurrence of an item equal to the specified
// item from the table.
//
template <class T> Bool CmTHashTable<T>::remove(const T& rObj)
{
  if (!_funcSet) return FALSE;
  unsigned idx = (*_hFunc)(rObj, _size);
  Bool success = _buckets[idx].remove(rObj);
  if (success) _total--;
  return success;
}


// "lookup" returns the first occurrence of an item equal to the specified
// item.
//
template <class T> const T& CmTHashTable<T>::lookup(const T& rObj) const
{
  if (!_funcSet) return _error;
  unsigned idx = (*_hFunc)(rObj, _size);
  T* out = _buckets[idx].lookup(rObj);
  return (out) ? *out : _error;
}


// "contains" checks if an item equal to the specified item exists
// in the table.
//
template <class T> Bool CmTHashTable<T>::contains(const T& rObj) const
{
  if (!_funcSet) return FALSE;
  unsigned idx = (*_hFunc)(rObj, _size);
  return _buckets[idx].contains(rObj);
}


// "occurrences" counts the number of items in the table equal to the
// specified item.
//
template <class T> unsigned CmTHashTable<T>::occurrences(const T& rObj) const
{
  CmTHashTableIterator<T> iterator(*this);
  unsigned                num = 0;
  while (!iterator.done())
    if (iterator.next() == rObj) num++;
  return num;
}


// "removeAll" removes all items from the table.
//
template <class T> void CmTHashTable<T>::removeAll()
{
  for (int ii = 0; ii < _size; ii++)
    _buckets[ii].removeAll();
  _total = 0;
}


// "resize" resizes the hash table.
//
template <class T> Bool CmTHashTable<T>::resize(unsigned newSize)
{
  if (newSize <= 0) newSize = 1;

  int               newTotal   = 0;
  CmTHashBucket<T> *newBuckets = new CmTHashBucket<T>[newSize];
  if (!newBuckets) return FALSE;

  CmTHashTableIterator<T> iterator(*this);
  while (!iterator.done())
  {
    T   item = iterator.next();
    int idx  = (*_hFunc)(item, newSize);
    newBuckets[idx].append(item);
    newTotal++;
  }

  delete[] _buckets;
  _size    = newSize;
  _buckets = newBuckets;
  _total   = newTotal;
  return TRUE;
}

// "isEmpty" checks whether or not the table is empty.
//
template <class T> Bool CmTHashTable<T>::isEmpty() const
{
  Bool empty = TRUE;
  int  ii    = 0;
  while (ii < _size && empty == TRUE)
    if (_buckets[ii].size() > 0) empty = FALSE;
  return empty;
}


// "newIterator" creates and returns a new table iterator.
//
template <class T> CmTIterator<T>* CmTHashTable<T>::newIterator() const
{
  return new CmTHashTableIterator<T>(*this);
}


// "append" appends a new item to the hash bucket.
//
template <class T> Bool CmTHashBucket<T>::append(const T& rObj)
{
  CmTHashNode<T> *newnode = new CmTHashNode<T>(rObj);
  if (!newnode) return FALSE;

  if (!_first)
    _first = _last = newnode;
  else
  {
    _last->_next = newnode;
    _last        = newnode;
  }
  _size++;
  return TRUE;
}


// "contains" checks if an item equal to the specified item exists
// in this hash bucket.
//
template <class T> Bool CmTHashBucket<T>::contains(const T& rObj) const
{
  CmTHashNode<T> *rover = _first;
  Bool            found = FALSE;
  while (rover && !found)
  {
    if (rover->_data == rObj) found = TRUE;
    else                      rover = rover->_next;
  }
  return found;
}


// "remove" removes the first occurrence of an item equal to the
// specified item from this hash bucket.
//
template <class T> Bool CmTHashBucket<T>::remove(const T& rObj)
{
  if (!_first) return FALSE;

  if (_first->_data == rObj)                // Object is first in the list.
  {
    CmTHashNode<T> *temp = _first;
    if (_first == _last) _first = _last = NULL;
    else                 _first = _first->_next;
    _size--;
    delete temp;
    return TRUE;
  }

  CmTHashNode<T> *rover1 = _first;          // Search for object in list.
  CmTHashNode<T> *rover2 = _last;

  while (rover1 != NULL && rover1->_data != rObj)
  {
    rover2 = rover1;
    rover1 = rover1->_next;
  }

  if (rover1 == NULL) return FALSE;         // Object was not found.

  if (rover1 == _last)                      // Object is last in list.
  {
    _last         = rover2;
    rover2->_next = NULL;
  }

  else                                      // Remove object from list.
    rover2->_next = rover2->_next->_next;

  delete rover1;                            // Delete the hash node.
  return TRUE;
}


// "lookup" returns the first occurrence of an item equal to the
// specified item.
//
template <class T> T* CmTHashBucket<T>::lookup(const T& rObj) const
{
  CmTHashNode<T> *rover = _first;
  CmTHashNode<T> *temp  = NULL;
  while (rover && !temp)
  {
    if (rover->_data == rObj)
      temp = rover;
    else
      rover = rover->_next;
  }
  return (temp) ? &(temp->_data) : NULL;
}


// "removeAll" removes all items from this hash bucket.
//
template <class T> void CmTHashBucket<T>::removeAll()
{
  CmTHashNode<T> *temp, *rover = _first;
  while (rover)
  {
    temp = rover->_next;
    delete rover;
    rover = temp;
  }
  _size  = 0;
  _first = _last = NULL;
}


// "CmTHashTableIterator" is the iterator constructor.  The node
// pointer is positioned at the first bucket containing items.
//
template <class T>
CmTHashTableIterator<T>::CmTHashTableIterator(const CmTHashTable<T>& Tb)
                        : _table(Tb), _bucket(0), _node(NULL)
{
  while (_table._buckets[_bucket]._size == 0 && _bucket < _table._size)
    _bucket++;
  if (_bucket < _table._size) _node = _table._buckets[_bucket]._first;
}


// "done" checks if the iterator can advance any further.
//
template <class T> Bool CmTHashTableIterator<T>::done() const
{
  return (!_node);
}


// "next" returns the current item and advances the iterator to the
// next item.
//
template <class T> const T& CmTHashTableIterator<T>::next()
{
  if (!_node) return _table._error;

  const T& rObj = _node->_data;         // Save current item reference.

  if (_node->_next)                     // Advance to next node.
    _node = _node->_next;
  else                                  // Advance to next bucket with items.
  {
    _bucket++;
    while (_bucket < _table._size && _table._buckets[_bucket]._size == 0)
      _bucket++;
    if (_bucket < _table._size) _node = _table._buckets[_bucket]._first;
    else                        _node = NULL;
  }
  return rObj;
}


// "previous" decrements the iterator by one object and then returns
// that object.
//
template <class T> const T& CmTHashTableIterator<T>::previous()
{
  if (!_node) return _table._error;
  const T& rval = _node->_data;

  if (_node == _table._buckets[_bucket]._first)
  {
    --_bucket;
    while (_bucket >= 0 && _table._buckets[_bucket]._size == 0)
      _bucket--;
    if (_bucket >= 0) _node = _table._buckets[_bucket]._last;
    else              _node = NULL;
  }
  else
  {
    CmTHashNode<T> *rover = _table._buckets[_bucket]._first;
    while (rover && rover->_next != _node)
      rover = rover->_next;
    _node = rover;
  }
  return rval;
}


// "current" returns the current object.
//
template <class T> const T& CmTHashTableIterator<T>::current() const
{
  return (_node) ? _node->_data : _table._error;
}


// "first" moves the iterator to the first item.
//
template <class T> void CmTHashTableIterator<T>::first()
{
  _bucket = 0;
  _node   = NULL;
  while (_table._buckets[_bucket]._size == 0 && _bucket < _table._size)
    _bucket++;
  if (_bucket < _table._size) _node = _table._buckets[_bucket]._first;
}


// "last" moves the iterator to the last item.
//
template <class T> void CmTHashTableIterator<T>::last()
{
  _bucket = _table._size - 1;
  _node   = NULL;
  while (_bucket >= 0 && _table._buckets[_bucket]._size == 0)
    _bucket--;
  if(_bucket >= 0) _node = _table._buckets[_bucket]._last;
}